package com.hoppinzq.algorithm.stackAndQueue;

import java.util.Iterator;

/**
 * 队列
 * FIFO 先进先出
 * 底层是链表
 * @param <T>
 */
public class MyQueue<T> implements Iterable<T>{
    private int N;
    private Node first;
    private Node last;
    private class Node{
        private Node next;
        public T data;
        public Node(Node next,T data){
            this.next=next;
            this.data=data;
        }
    }

    public MyQueue(){
        this.N=0;
        this.first=new Node(null,null);
        this.last=null;
    }

    public boolean isEmpty() {
        return N==0;
    }

    public int length() {
        return N;
    }

    /**
     * 存入队列
     * @param data
     */
    public void enQueue(T data){
        if(last==null){
            last=new Node(null,data);
            first.next=last;
        }else{
            Node oldLast=last;
            last=new Node(null,data);
            oldLast.next=last;
        }
        N++;
    }

    /**
     * 从队列中移除，并返回被移除的值
     * @return
     */
    public T deQueue(){
        if(first.next==null){
            return null;
        }
        Node node=first.next;
        first.next=node.next;
        N--;
        if(isEmpty()){
            last=null;
        }
        return node.data;
    }

    @Override
    public Iterator<T> iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator{
        private Node n;

        public QIterator(){
            this.n=first;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.data;
        }
    }
}
